package dujiu.leetcode.graph;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class dfs {

    static List<List<Integer>> result = new ArrayList<>(); // 收集符合条件的路径
    static List<Integer> path = new ArrayList<>(); // 1节点到终点的路径

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();// n个节点
        int m = scanner.nextInt(); // m条边

        int[][] graph = new int[n+1][n+1];
        // graph[n+1][n+1] = 0;

        while (m-- > 0){
            int s = scanner.nextInt();
            int t = scanner.nextInt();
            graph[s][t] = 1;
        }

        path.add(1); // 每条路径都是从1开始出发
        dfs(graph,1,n); // 开始遍历
        if (result.isEmpty()){
            System.out.println(-1);
        }
        for (List<Integer> list : result) {
            for (int i = 0; i < list.size()-1; i++) {
                System.out.print(list.get(i) + " ");
            }
            System.out.print(list.get(list.size()-1));
            System.out.println();
        }
    }

    public static void dfs(int[][] graph, int x, int n){
        if (x == n){
            result.add(new ArrayList<>(path));
            // result.add(path);
            return;
        }

        for (int i = 0; i <= n; i++) {
            if (graph[x][i] == 1){
                path.add(i); // 将遍历到的节点加入路径
                dfs(graph,i,n);
                path.remove(path.size()-1);
            }
        }
    }
}
